package _11_整理题目._1_链表指针._翻转链表;

import org.junit.Test;
import util.ListNode;

/**
 * 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
 * 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
 * 你不能更改节点中的值，只能更改节点本身。
 * 要求空间复杂度 O(1)
 * 
 * 例如：
 * 给定的链表是1 2 3 4 5
 * 对于 k=2, 你应该返回 2 1 4 3 5
 * 对于 k=3, 你应该返回 3 2 1 4 5
 * 
 * 找到 k 个节点并翻转 + 递归拼接
 * 确定 k 个节点的 head 和 tail，根据 head tail 翻转链表，返回的是 newHead
 * 一定要注意，
 *      翻转之前的 head 变为了反转之后的 tail，
 *      翻转之前的 tail 变为了下一轮要翻转的 head，
 *      利用递归，这次的翻转连接下一次的翻转，head.next = reverseKGroup(tail, k)
 * 
 * 
 * for (int i = 0; i < k; i++)  等价于  while(k-- > 0)  都是执行 k 次
 * 
 */
public class _01_链表中的节点每k个一组翻转 {
    
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            if (tail == null) return head;
            tail = tail.next;
        }
        
        ListNode newHead = reversePart(head, tail);
        head.next = reverseKGroup(tail, k);
        return newHead;
    }
    
    private ListNode reversePart(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != tail) {
            ListNode nex = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
    
    @Test
    public void main() {
        Integer[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        ListNode head = ListNode.getListFromArray(array);
        ListNode.printList(head);
        ListNode result = reverseKGroup(head, 4);
        ListNode.printList(result);
    }
}
